//
// Created by zhou on 2023/6/4.
// 拓扑排序

#include "stdio.h"
#include "stdlib.h"

#define MAXVEX 20
#define ERROR 0
#define OK 1

// 边表节点
typedef struct EdgeNode{
    // 邻接点域，存储该顶点对应的下标
    int adjvex;
    // 权值
    int weight;
    // 链域，指向下一个邻接点
    struct EdgeNode *next;
}EdgeNode;

// 顶点表结点
typedef struct VertexNode{
    // 入度
    int in;
    // 顶点信息
    int data;
    // 边表头指针
    struct EdgeNode *firstEdge;
}VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numNodes, numEdges;
}graphAdjList, *GraphAdjList;

/**
 * 拓扑排序
 * @param GL 邻接表
 * @return 若GL无回路，返回1，否则返回0
 */
int TopologicalSort(GraphAdjList GL) {
    // 用于遍历邻接表的指针
    EdgeNode *e;
    int i,k,gettop;
    // 栈指针域下标
    int top = 0;
    // 统计输出的顶点个数
    int count = 0;
    // 建栈用于将入度为0的顶点入栈
    int *stack;
    // 分配栈空间
    stack = (int*)malloc(GL->numNodes * sizeof (int));
    // 遍历所有顶点，将顶点入度为0的入栈
    for(i = 0; i < GL->numNodes; i++) {
        if(0 == GL->adjList[i].in) {
            stack[++top] = i;
        }
    }
    // 当栈指针下标不为0时，代表栈中有顶点
    while (top != 0) {
        // 栈顶的顶点出栈
        gettop = stack[top--];
        printf("%d->", GL->adjList[gettop].data);
        // 记录下出栈的顶点数
        count++;
        // 遍历此顶点的所有邻接点
        for (e = GL->adjList[gettop].firstEdge; e; e = e->next) {
            // 将这些邻接点的入度减1（实际上就是断掉边）
            k = e->adjvex;
            // 若入度减少后刚好为0，则再将该顶点入栈
            if(!(--GL->adjList[k].in)) {
                stack[++top] = k;
            }
        }
    }
    // 输出顶点数与总顶点数不一致，说明有环
    if(count < GL->numNodes) return ERROR;
    else return OK;
}